//三步问题。有个小孩正在上楼梯，楼梯有 n 阶台阶，小孩一次可以上 1 阶、2 阶或 3 阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要
//对结果模 1000000007。 
//
// 示例 1： 
//
// 
// 输入：n = 3 
// 输出：4
// 说明：有四种走法
// 
//
// 示例 2： 
//
// 
// 输入：n = 5
// 输出：13
// 
//
// 提示: 
//
// 
// n 范围在[1, 1000000]之间 
// 
//
// Related Topics 记忆化搜索 数学 动态规划 👍 130 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-07-17 00:10:33
 * @description 面试题 08.01.三步问题
 */
public class ThreeStepsProblemLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 ThreeStepsProblemLcci fun=new ThreeStepsProblemLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int waysToStep(int n) {
        if(n<=2) return n;
		if(n==3) return 4;
		int a1=1,a2=2,a3=4;
		for(int i=4;i<=n;i++){
			int temp = ((a1 + a2)% 1000000007 + a3) % 1000000007;
			a1 = a2;
			a2 = a3;
			a3 = temp;
		}
		return a3;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
